package com.future;

/**
 * Description:
 * ����һ������?n + 1 ������������?nums �������ֶ���?[1, n]?��Χ�ڣ����� 1 �� n������֪���ٴ���һ���ظ���������
 * <p>
 * ���� nums ֻ�� һ���ظ������� ������?����ظ����� ��
 * <p>
 * ����ƵĽ���������� ���޸� ���� nums ��ֻ�ó����� O(1) �Ķ���ռ䡣
 * <p>
 * ʾ�� 1��
 * <p>
 * ���룺nums = [1,3,4,2,2]
 * �����2
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode.cn/problems/find-the-duplicate-number
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @author weiruibai.vendor
 * Date: 2022/5/12 16:12
 */
public class Solution_287 {

    public static void main(String[] args) {
        int[] nums = {1, 3, 4, 2, 2};
        nums = new int[]{3, 1, 3, 4, 2};

        System.out.println(findDuplicate(nums));
    }

    /**
     * ���±�i=0����
     * 1�������Ӧ��ֵ
     *
     * @param nums
     * @return
     */
    public static int findDuplicate(int[] nums) {
        int cur = 0;
        int N = nums.length;
        while (cur < N) {
            int val = nums[cur];
            if (val == cur + 1) {
                /**
                 * �±��Ӧ��ֵλ�ö�Ӧ��ֱ��������һ��λ��
                 */
                cur++;
            } else if (val < cur + 1 || nums[val - 1] == val) {
                /**
                 * nums[val - 1] == val��������磺{3, 1, 3, 4, 2}
                 * ��i=0,��Ӧ��ֵΪ3�����յ���Ӧ�ý���λ��0��2��3-1��������λ��2����ҲΪ3�����½�����ѭ�������
                 */
                return val;
            } else {
                /**
                 * ���±�Ϊcur�ŵ��ó��ֵ�λ��
                 */
                swap(nums, cur, val - 1);
            }
        }
        return -1;
    }

    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
